package main

func change(amount int, coins []int) int {
	dp := make([][]int, len(coins))
	for i := range dp {
		dp[i] = make([]int, amount+1)
	}
	for i := 0; i <= amount; i += coins[0] {
		dp[0][i] = 1
	}

	for i := 1; i < len(coins); i++ {
		for j := 0; j <= amount; j++ {
			ways := 0
			if j >= coins[i] {
				ways = dp[i][j-coins[i]]
			}

			dp[i][j] = dp[i-1][j] + ways
		}
	}

	return dp[len(coins)-1][amount]
}
